package com.kk.demo.unsface;

import java.util.Arrays;
import java.util.Random;

public class ArrayQuickSoft {

    public int spit(int[] array, int left, int right) {
        int mid = array[left];

        while (left < right) {
            // 与中轴的数据比较，比中轴小的放左边
            while (left < right && array[right] >= mid) {
                right--;
            }

            array[left] = array[right];

            // 与中轴的数据比较，比中轴大的放右边
            while (left < right && array[left] <= mid) {
                left++;
            }
            array[right] = array[left];
        }

        // 记录中轴位置
        array[left] = mid;

        return left;
    }

    public void sort(int[] list, int left, int right) {
        if (left < right) {
            int parrent = this.spit(list, left, right);

            sort(list, left, parrent - 1);

            sort(list, parrent + 1, right);
        }

    }

    private static final Random random = new Random();

    public static void main(String[] args) {

        //
        ArrayQuickSoft soft = new ArrayQuickSoft();
        // int index = soft.spit(array, 0, array.length - 1);

        // System.out.println("中心点的坐标:" + index);
        // System.out.println("中心点的值:" + array[index]);
        // System.out.println(Arrays.toString(array));

        int size = 10000;

        int[] array = new int[size];

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(10000);
        }

        long startTime = System.currentTimeMillis();

        soft.sort(array, 0, array.length - 1);

        long endTime = System.currentTimeMillis();

        System.out.println("快速排序时间:" + (endTime - startTime));
        

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(10000);
        }

        long startTime2 = System.currentTimeMillis();

        Arrays.sort(array);

        long endTime2 = System.currentTimeMillis();

        System.out.println("自带排序时间:" + (endTime2 - startTime2));

    }

}
